#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <wchar.h>
#include <time.h>

#include "../src/rxpoly.h"

// #define CHECK( arg ) check( arg, __LINE__ )

int main()
{
	wprintf( L"Test for zero-length string match...\t" );
	assert( matches( L"6LU+6ŽLUŽŤOUČKÝ KˇŮŇščřvca $\\$&$Łł&Ł", L"", RF_EXTENDED ) );
	wprintf( L"\tOK\n" );

	wprintf( L"Tests for literal regexp...\t" );
	assert( matches( L"a", L"a", RF_BASIC ) );
	assert( matches( L"a", L"a", RF_EXTENDED ) );
	assert( ! matches( L"a", L"A", RF_EXTENDED ) );
	assert( matches( L"a", L"A", RF_EXTENDED | RF_ICASE ) );
	assert( matches( L"a", L"(a)", RF_EXTENDED ) );
	assert( ! matches( L"a", L"(a)", RF_BASIC ) );
	assert( matches( L"(a)", L"(a)", RF_BASIC ) );
	assert( matches( L"a", L"\\(a\\)", RF_BASIC ) );
	assert( matches( L"a", L"(((((a)))))", RF_EXTENDED ) );
	assert( ! matches( L"a", L"(((((A)))))", RF_EXTENDED ) );
	assert( matches( L"bde", L"((a|(b(c|d)e)))", RF_EXTENDED ) );
	assert( matches( L"ab", L"ab", RF_EXTENDED ) );
	assert( matches( L"ab", L"\\w[^[:blank:]]", RF_EXTENDED ) );
	assert( matches( L"ab", L"a(b)", RF_EXTENDED ) );
	assert( matches( L"ab", L"a[^a]", RF_EXTENDED ) );
	assert( matches( L"ab", L"a[^a]", RF_BASIC | RF_ICASE ) );
	assert( ! matches( L"aA", L"a[^a]", RF_BASIC | RF_ICASE ) );
	assert( matches( L"abcdef", L"a(b)c((d).)f", RF_EXTENDED ) );
	assert( ! matches( L"abCdef ", L"a(b)c((d).)f", RF_EXTENDED ) );
	assert( matches( L"ba", L"a", RF_EXTENDED ) );
	assert( ! matches( L"baobabaababa", L"bababa", RF_EXTENDED ) );
	assert( matches( L"baobabaababa", L"aababa", RF_EXTENDED ) );
	assert( matches( L"ab", L"(a)(b)", RF_EXTENDED ) );
	assert( matches( L"baobabaababa", L"a(((a)(ba))ba)", RF_EXTENDED ) );
	assert( matches( L"abcdefghikjlmnop", L"................", RF_EXTENDED ) );
	assert( ! matches( L"abcdefghikjlmnop", L".................", RF_EXTENDED ) );
	wprintf( L"\tOK\n" );

	wprintf( L"Tests for non-nested repetitions...\t" );

	assert( matches( L"baa", L"a*", RF_EXTENDED ) );
	assert( matches( L"", L"a*", RF_EXTENDED ) );
	assert( matches( L"b", L"a*", RF_EXTENDED ) );

	assert( matches( L"baa", L"aa*", RF_EXTENDED ) );
	assert( ! matches( L"", L"aa*", RF_EXTENDED ) );
	assert( ! matches( L"b", L"aa*", RF_EXTENDED ) );

	assert( matches( L"baa", L"(aa){1,}", RF_EXTENDED ) );
	assert( ! matches( L"", L"(aa){1,}", RF_EXTENDED ) );
	assert( ! matches( L"b", L"(aa){1,}", RF_EXTENDED ) );

	assert( matches( L"baa", L"(aa|b){2,2}", RF_EXTENDED ) );
	assert( matches( L"baa", L"((a)|(b)){2,2}", RF_EXTENDED ) );
	assert( matches( L"baa", L"(aa|(b)){2,2}", RF_EXTENDED ) );
	assert( ! matches( L"baba", L"(aa|b){2,2}", RF_EXTENDED ) );
	assert( matches( L"baaba", L"(aa|b){2,2}", RF_EXTENDED ) );
	assert( matches( L"baaba", L"(a(a)|b){2,2}", RF_EXTENDED ) );
	assert( matches( L"baaba", L"b(a(a)|b){2,2}", RF_EXTENDED ) );
	assert( ! matches( L"baaa", L"b(a(a)|b){2,2}", RF_EXTENDED ) );

	assert( matches( L"x", L"xc*d*", RF_EXTENDED ) );

	assert( matches( L"bacabacababaabca", L"((((a(a)|b){2,2})))", RF_EXTENDED ) );
	assert( ! matches( L"bacabacababaabca", L"((((a(a)|b){4,})))", RF_EXTENDED ) );

	assert( matches( L"abbc", L"ab{1,2}c", RF_EXTENDED ) );
	assert( ! matches( L"abbbc", L"ab{1,2}c", RF_EXTENDED ) );

	assert( matches( L"ab", L"a{1}b{1}", RF_EXTENDED ) );
	assert( matches( L"baba", L"a{1,2}a*b{1}", RF_EXTENDED ) );
	assert( matches( L"baba", L"(a{1,2})((a)*b{1})", RF_EXTENDED ) );
	assert( matches( L"abcca", L"bc{2,2}", RF_EXTENDED ) );
	assert( matches( L"XXXaabcccdXXaabcccddX", L"a{2}bc{3}d{1,2}d", RF_EXTENDED ) );
	assert( ! matches( L"XXXaabcccdXXaabcccdX", L"a{2}bc{3}d{1,2}d", RF_EXTENDED ) );

	assert( matches( L"abbcccd", L"ab{1,2}c{0,3}d", RF_EXTENDED ) );
	assert( ! matches( L"abbbccccd", L"ab{1,2}c{0,3}d", RF_EXTENDED ) );

	wprintf( L"\tOK\n" );


	wprintf( L"Tests for nested repetitions...\t" );

	assert( matches( L"aa", L"(a{1}){2,4}", RF_EXTENDED ) );
	assert( matches( L"aa", L".**", RF_EXTENDED ) );
	assert( matches( L"aa", L".***", RF_EXTENDED ) );
	assert( matches( L"aa", L"(.*)**", RF_EXTENDED ) );
	assert( matches( L"aa", L"(ab*)*", RF_EXTENDED ) );
	assert( matches( L"aa", L"(a(b)*)*", RF_EXTENDED ) );
	assert( matches( L"aa", L"(a(b*))*", RF_EXTENDED ) );
	assert( matches( L"aa", L"(a*b*)*", RF_EXTENDED ) );
	assert( matches( L"a", L"(a*(.*)*)*", RF_EXTENDED ) );
	assert( matches( L"a", L"(a*(.*){1,})*", RF_EXTENDED ) );
	assert( matches( L"", L"(a*(.*){1,})*", RF_EXTENDED ) );
	assert( matches( L"abcabcd", L"(a{1,2}bc){2,4}", RF_EXTENDED ) );
	assert( matches( L"abcbcd", L"(a*bc){2,4}", RF_EXTENDED ) );
	assert( ! matches( L"abcbad", L"(a*bc){2,4}", RF_EXTENDED ) );
	assert( matches( L"bbc", L"(bc*){2,4}", RF_EXTENDED ) );
	assert( matches( L"bccbc", L"(bc*){2,4}", RF_EXTENDED ) );
	assert( matches( L"abcaccbc", L"(b(a|c)*){2,4}", RF_EXTENDED ) );
	assert( ! matches( L"abcdccbc", L"(b(a|c)*){2,4}", RF_EXTENDED ) );
	assert( matches( L"acbbcd", L"(bc*){2,4}", RF_EXTENDED ) );
	assert( matches( L"baabcd", L"(a*b){2,4}", RF_EXTENDED ) );
	assert( matches( L"aabbcd", L"(a*b){2,4}", RF_EXTENDED ) );
	assert( matches( L"abcaaabcd", L"(a*bc){2,4}", RF_EXTENDED ) );
	assert( matches( L"abcaaabcd", L"(aa?a?bc){2,4}", RF_EXTENDED ) );
	assert( ! matches( L"abcabaabcd", L"(a*bc){2,4}", RF_EXTENDED ) );
	assert( matches( L"bb", L"(a*b){1,2}(a*b){1,2}", RF_EXTENDED ) );
	assert( matches( L"bbbb", L"(a*b){2,4}(a*b){2,4}", RF_EXTENDED ) );
	assert( matches( L"babbab", L"(a*b){2,4}(a*b){2,4}", RF_EXTENDED ) );
	assert( matches( L"efgdaddabcaaabcd", L"g(d(a|d)){1,2}", RF_EXTENDED ) );
	assert( matches( L"efgdaddabcaaabcd", L"g(d(a|d)){1,2}(a*bc){2,4}", RF_EXTENDED ) );
	assert( matches( L"efgdaddaabcaaabcd", L"g(d(a|d)){1,2}(aaa*bc){2,4}", RF_EXTENDED ) );
	assert( ! matches( L"efgdadaddabcaaabcd", L"g(d(a|d)){1,2}(a*bc){2,4}", RF_EXTENDED ) );

	assert( matches( L"a", L"a{1}{1}", RF_EXTENDED ) );
	assert( matches( L"a", L"a{1}{1,4}", RF_EXTENDED ) );
	assert( matches( L"ab", L"a{1}{1,4}b", RF_EXTENDED ) );
	assert( matches( L"aab", L"a{2}{1}b", RF_EXTENDED ) );
	assert( matches( L"aab", L"a{2}{1,4}b", RF_EXTENDED ) );
	assert( matches( L"XXXaabcccdXXaabcccddX", L"a{2}bc{3}{1,2}dd", RF_EXTENDED ) );

	assert( matches( L"", L"(a*(b*))c*(d*(e*)*)", RF_EXTENDED ) );
	assert( ! matches( L"", L"(a*(b*))xc*(d*(e*)*)", RF_EXTENDED ) );

	assert( matches( L"a", L"(a*(.*)*)*", RF_EXTENDED ) );
	assert( matches( L"x", L"xc*(d*(e*)*)", RF_EXTENDED ) );
	assert( matches( L"x", L"(a*(b*))xc*(d*(e*)*)", RF_EXTENDED ) );
	assert( matches( L"abxccced", L"(a*(b*))xc*(d*(e*))*", RF_EXTENDED ) );
	assert( matches( L"abxcccedded", L"(a*(b*))xc*(d*(e*))*", RF_EXTENDED ) );

	wprintf( L"\tOK\n" );


	wprintf( L"Tests for anchors...\t" );

	assert( matches( L"a", L"^a$", RF_EXTENDED ) );
	assert( matches( L"", L"^$", RF_EXTENDED ) );
	assert( ! matches( L"ba", L"^a", RF_EXTENDED ) );
	assert( ! matches( L"ba", L"b$a", RF_EXTENDED ) );
	assert( ! matches( L"ba", L"b^a", RF_EXTENDED ) );

	assert( matches( L"ba", L"a$$$", RF_EXTENDED ) );
	assert( ! matches( L"ba", L"^$^ba$$$", RF_EXTENDED ) );
	assert( matches( L"", L"^$^$$$", RF_EXTENDED ) );

	assert( matches( L"aab", L"(aa|b)$", RF_EXTENDED ) );
	assert( matches( L"aab", L"(aaa|b$)", RF_EXTENDED ) );
	assert( ! matches( L"aab", L"(aa$|^b)", RF_EXTENDED ) );
	assert( matches( L"aab", L"(a?^a|$b)", RF_EXTENDED ) );
	assert( matches( L"aab", L"(a?^aa?|b$){1,2}", RF_EXTENDED ) );

	wprintf( L"\tOK\n" );

/*
 *	wprintf( L"Tests for \"&\"...\t" );
 *
 *	assert( matches( L"a", L"a&a", RF_EXTENDED ) );
 *	assert( matches( L"a", L".*&a", RF_EXTENDED ) );
 *	assert( ! matches( L"ab", L"a&b", RF_EXTENDED ) );
 *
 *	assert( matches( L"a", L"a&a&a", RF_EXTENDED ) );
 *	assert( matches( L"a", L"(a&a)", RF_EXTENDED ) );
 *	assert( matches( L"a", L"a&(a)&a", RF_EXTENDED ) );
 *	assert( matches( L"a", L"a&(a&a)&a", RF_EXTENDED ) );
 *	assert( ! matches( L"a", L".*&a&(b)&a", RF_EXTENDED ) );
 *	assert( matches( L"a", L".*&a&(b|(a&.))&a", RF_EXTENDED ) );
 *
 *	assert( matches( L"abc", L"^&.(b|c){2,}", RF_EXTENDED ) );
 *	assert( ! matches( L"abc", L"^&(b|c){2,}", RF_EXTENDED ) );
 *	assert( ! matches( L"abc", L"^&.(b|c){2,}&b", RF_EXTENDED ) );
 *
 *	assert( matches( L"abcdfoobarefg", L"f(o*&oo(b|c)ar)&......efg$", 
 *	RF_EXTENDED ) );
 *	assert( ! matches( L"abcdfoobarefg", L"f(o*&oo(b|c)ar)&.....efg$", 
 *	RF_EXTENDED ) );
 *
 *	assert( matches( L"aa", L"(a{1}){2,4}&a", RF_EXTENDED ) );
 *	assert( matches( L"aa", L"a&(a{1}){2,4}&a", RF_EXTENDED ) );
 *	assert( matches( L"ggabcaaabcd", L"a&(aa?a?bc){2,4}", RF_EXTENDED ) );
 *	assert( matches( L"bb", L"(a*b){2,4}&(a*b){2,4}", RF_EXTENDED ) );
 *	assert( matches( L"bab", L"b&(a*b){2,4}", RF_EXTENDED ) );
 *	assert( matches( L"bab", L"(a*b){2,4}&b", RF_EXTENDED ) );
 *	assert( ! matches( L"bab", L"(a*b){2,4}&a", RF_EXTENDED ) );
 *	assert( matches( L"bb", L"(a*b){2,4}&(a*b){2,4}", RF_EXTENDED ) );
 *	assert( matches( L"bab", L"(a*b){2,4}&(a*b){2,4}", RF_EXTENDED ) );
 *	assert( matches( L"abaab", L"(a*b){2,4}&(a*b){2,4}", RF_EXTENDED ) );
 *	assert( matches( L"ab", L"a*&a", RF_EXTENDED ) );
 *	assert( matches( L"ab", L"a*&b", RF_EXTENDED ) );
 *	assert( matches( L"ab", L"a*b&ab", RF_EXTENDED ) );
 *	assert( matches( L"abab", L"(a*b){2,4}&(ab){2,4}", RF_EXTENDED ) );
 *	assert( matches( L"ggabcaaabcd", L"(a*bc){2,4}&(aa?a?bc){2,4}", RF_EXTENDED 
 *	) );
 *	assert( matches( L"ggabcaaabcd", L"(a*bc){2,4}&(ax*a?a?bc){2,4}", 
 *	RF_EXTENDED ) );
 *	assert( ! matches( L"ggabcaaabcd", L"(a*bc){2,4}&(gax*a?a?bc){2,4}", 
 *	RF_EXTENDED ) );
 *	assert( ! matches( L"ggabcaaabcd", L"(a*bc){2,4}&g(ax*a?a?bc){2,4}", 
 *	RF_EXTENDED ) );
 *	assert( ! matches( L"ggabcaaabcd", L"gg(a*bc){2,4}&g(ax*a?a?bc){2,4}", 
 *	RF_EXTENDED ) );
 *
 *	wprintf( L"\tOK\n" );
 *
 *	( 'assert( !matches( L"aab", L"(aa&a)b", RF_EXTENDED ) )' would cause 
 *	a problem now. )
 */

	wprintf( L"Tests for complexity...\n" );
	clock_t start;

	start = clock();
	assert( matches( L"aa", L"(ab*|aab*)(aab*|ab*)", RF_EXTENDED ) );
	wprintf( L"\t1\t... %g s\n", ((double) (clock() - start)) / CLOCKS_PER_SEC ), fflush( stdout );

	start = clock();
	assert( matches( L"aaaa", L"(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)", RF_EXTENDED ) );
	wprintf( L"\t2\t... %g s\n", ((double) (clock() - start)) / CLOCKS_PER_SEC ), fflush( stdout );

	start = clock();
	assert( matches( L"aaaaaaaa", L"(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)", RF_EXTENDED ) );
	wprintf( L"\t4\t... %g s\n", ((double) (clock() - start)) / CLOCKS_PER_SEC ), fflush( stdout );

	/*
	start = clock();
	assert( matches( L"aaaaaaaaaaaaaaaa",
				L"(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)", RF_EXTENDED ) );
	wprintf( L"\t8\t... %g s\n", ((double) (clock() - start)) / CLOCKS_PER_SEC ), fflush( stdout );

	start = clock();
	assert( matches( L"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
				L"(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)", RF_EXTENDED ) );
	wprintf( L"\t16\t... %g s\n", ((double) (clock() - start)) / CLOCKS_PER_SEC ), fflush( stdout );

	start = clock();
	assert( matches( L"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
				L"(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)", RF_EXTENDED ) );
	wprintf( L"\t32\t... %g s\n", ((double) (clock() - start)) / CLOCKS_PER_SEC ), fflush( stdout );
	*/

/*
 * Following test takes too long to complete. However, using a debugger, one can 
 * see in the previous tests rather moderate grow in number of candidates by 
 * each regex's node. That's good news.
 *
	start = clock();
	assert( matches( L"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
				L"(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)(ab*|aab*)(aab*|ab*)", RF_EXTENDED ) );
	wprintf( L"\t64\t... %g s\n", ((double) (clock() - start)) / CLOCKS_PER_SEC ), fflush( stdout );
	*
	*
	*/

	wprintf( L"\tOK\n" );


	wprintf( L"Tests for matches() finished.\n" );
	return 0;
}

// int check( int errno, int line )
// {
// 	if( errno != 0 )
// 		fprintf( stderr, "Error \"%d\" in line number %d.\n", strerror( -errno ), line );
// }
